# -*- coding=utf-8-*-
"""
@File:memory_selection
@Author:Created by Han X.Y
@Date:on 2021/7/14 8:54 
"""
"""
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

示例:

输入: [0,1,0,3,12]
输出: [1,3,12,0,0]
说明:

必须在原数组上操作，不能拷贝额外的数组。
尽量减少操作次数。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/move-zeroes
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。


"""


# class Solution:
#     def moveZeroes(self, nums) -> None:
#         """
#         Do not return anything, modify nums in-place instead.
#         """
#         i = 0
#         j = i + 1
#         while i < len(nums) and j < len(nums):
#             print(i, j, nums, nums[i], nums[j])
#             if nums[i] == 0 and nums[j] != 0:
#                 nums[i], nums[j] = nums[j], nums[i]
#             elif nums[i] == 0 and nums[j] == 0:
#                 j += 1
#                 # j=1+j if j==i else j
#             else:
#                 i += 1
#                 j += 1
#         return nums

class Solution(object):
    def moveZeroes(self, nums):
        """
        :type nums: List[int]
        :rtype: None Do not return anything, modify nums in-place instead.
        """
        if not nums:
            return 0
        # 两个指针i和j
        j = 0
        for i in range(len(nums)):
            # 当前元素!=0，就把其交换到左边，等于0的交换到右边
            if nums[i]:
                print(f"i={i},j={j},nums[i]={nums[i]},nums[j]={nums[j]},nums={nums}")
                nums[j], nums[i] = nums[i], nums[j]
                j += 1

        return nums


if __name__ == "__main__":
    s = Solution()
    nums1 = [0, 1, 0, 3, 12]
    nums2 = [4, 2, 4, 0, 0, 3, 0, 5, 1, 0]
    nums3 = [1642376570, -170806273, 0, 186670518, -1717197374, -755370052, 0, -2143144381, -2126916254, -2052753959, 0,
             78837363, 332377859, 0, 218377953, 679616852, -469921300, 618934575, -1197829068, 1164848220, 1136812672,
             260943961, -1717914159, 1988974091, -1600175456, 297538289, -1370841347, 1426065901, 1112093749,
             -1889106974,
             -1305560661, 1031328795, 1011122789, 1578059487, -981790313, -1703036707, 0, 0, -2024681995, -263268937,
             -1128404738, 585096076, -1297321501, 0, 25769844, 1191581344, 696920024, 1263666992, 1394984270,
             -438740064,
             397844203, 812691675, 1352094594, 1921710002, -1386244038, 1314259048, -1212982201, 231857423, -813215086,
             1791228429, -321818289, 724173972, 1709378004, -1465618809, 562680468, 986066537, 988738955, 1348398714,
             1584161196, 1204194837, 941623168, -100404437, 227588146, 1497711509, 42561089, 742618810, -614272961,
             920863382, 0, 1495424400, 0, -1595266076, -442498736, -578380367, 1880717888, 910108285, 1133376597,
             -1277901763, 929396605, 1841742538, 990364115, -635186133, -379656662, 2065901193, -848495571, -1482814604,
             -789996815, -249997267, -1541735366, 215572641, -1872542930, 1148191427, 1521741460, -591941452,
             -337042458,
             457943503, 1503956857, 1766844881, 973596415, -2123776953, 1757000275, 0, -1725059115, -1055554319,
             -334778952,
             927002791, -1559651348, -153011128, 211243048, 0, 1815747342, -1880059045, 0, 519725804, 1681980594, 0,
             -21481317, -919487171, -168450854, 1485789020, 670860182, 579138490, -1895196648, 450045964, 1595321017,
             982187038, 922454473, 0, -1470981055, 0, 2010068850, -1967650573, 1407367522, 914725193, -1953080746,
             -704647444, 709117023, -185420608, -360941049, -207208055, -1680003899, 1203565440, -1325907261,
             -1447918722,
             806419959, -1807977718, 0, 1757848817, -1801857429, 1361881876, 987533271, -1320319045, 1167833130,
             1426183095,
             1378796128, -1568153326, -813375755, -1174908282, 1773635329, 0, -1704902672, 2124040266, -1000608986,
             1567735422, -864930161, 2082029081, -1309827473, -496657229, 1156280646, 0, -1196687100, 373047346,
             -1151495499, 0, -2047539677, -1266014426, -590182077, 1138492766, -635145771, 285772696, 2109090359,
             -2000165411, 1726601766, -1656620665, -566204792, 1682338700, 1912899363, -1324838888, 1289083117,
             1977894099,
             200926627, 0, -1621512946, 1759107531, 1656198532, -1077285633, -185057361, -284871244, -658196264, 0,
             1419171394, 0, 2002764639, -1714255876, 1257793531, 65755812, -294025061, 810001172, -1808783221,
             -1466849562,
             1354629779, 2122489605, 1245260383, 0, 1969887370, -716189274, -1867770142, 1209771326, 248717944,
             -1554175004,
             1425090467, -1804562492, 898064692, 956388938, -476922859, 0, -503049526, -1270923898, -1025808204,
             1620350824,
             -368817250, 1815523350, 1014816057, 1211883140, -7587759, 1915741448, 1776719044, -1733775409, -707129298,
             -1002027276, 419367192, 1534033157, 0, 487916089, -317322202, 1534627959, -520556653, 1131421618,
             -132200895,
             -170489830, 283743890, -180136249, 1925767271, 0, 135587503, -1634761023, 1424866137, 958331684,
             -716270871,
             -126027378, 1314211283, 1336123048, -1228403960, 2092928590, 532500420, 1975871259, -94598042, -1664474369,
             1152791558, 0, 0, -1688521705, -1624020652, -1018477919, -874282140, 0, -879699091, -1949104465, 0, 0,
             268459483, -143585765, -1344256255, -678811087, 1228185574, 168640451, 0, -975873157, 1030868536,
             -1077347819,
             -1266127710, -1459801684, -1459020074, 0, -2134480401, 0, -1126194562, 0, 248624233, -1788518905, 0,
             1129435856, 0, 1348927979, 0, 548664690, 1620538116, 1626325812, 1202178086, -1642896628, 1195786616,
             1950772120, 887955178, 0, -1516498912, 961212451, 174791160, 290175089, 0, 525775977, 96279543, 663648376,
             1995572803, -2135987021, 401051857, 303808979, 651311038, 67812808, -923537610, -1970999084, 946845307,
             973308816, 123761551, 127001710, -419224857, -616573941, 1331984214, 1541173263, -850312370, 366141780,
             -657421261, -1546951526, 0, 624100172, 295752831, -1681541648, 1236994317, 1085930281, 687928903,
             816778475,
             -16138193, 528568079, -1824727339, -364926519, 1893763283, -1917224556, 0, -120622048, 1833230140,
             -1723423123,
             95997105, 165792638, -1029254101, 902562303, 1584457803, 85397969, -1698838340, -1088274761, -1144260871,
             553648802, -2134081622, 268483850, 2057164078, -185415805, 1351662853, 1422250855, 644068339, -921845694,
             958289405, -172292695, 180881025, -801504645, 505638533, -1483528836, -844727839, 1774696288, -1012034522,
             0,
             -1219402027, 1134436349, -1059400416, 427073911, -604174603, -1886066380, 1284592480, 731539480,
             1158692865,
             -158645387, 1074885412, -286520660, 0, 476944010, 314743980, 2088711238, 1435936700, 703686372, 566711369,
             -445527240, 2041740207, 1806745750, -371866351, 590374328, -1242648245, 813565457, 0, -1737667294,
             1798683372,
             -1874034035, 0, -735928120, 2040196350, 1266148764, -914060312, 1819734900, -1833737161, -1438668499, 0,
             1671983443, 0, 282932472, 105614276, 161365464, 216507142, -1386557943, -1879484865, 671268545, 2061299797,
             -990673175, 1858176493, -1621898843, 2124426179, -128447599, -1908223053, -795005950, -1525854142,
             -267488428,
             -1036272404, -866033189, -370741595, 0, 0, -2109519986, 0, 0, -70546121, -122624749, -1199903092,
             957467453,
             -33603698, -817275468, -864453284, 350118472, -264224154, 207280503, 316641044, -2062841606, 270130736,
             712893216, -1630100327, 721595642, -1787388607, 2026977089, -1179680929, -1054639541, 1294232465,
             366952576, 0,
             194508837, -2014782224, -1331237793, -761691653, -1135981471, -1025640224, -587846316, -1215155925,
             -1598182298, 1673878243, -2092292336, -555387652, -450117752, 72656779, 937431866, 2071365258, -2120515707,
             -1592323, 0, 1059495096, 528205076, 24825642, -403714586, 342801441, -2001724423, 274097926, 313193544,
             2084730029, 1975261738, -1269138137, -1702497854, -668986533, 0, -1293419497, -62388830, -1108575523,
             1360935923, 1284733493, 2036635350, 1922487883, -267962349, 2019022713, 1241214068, -1842879547, 802756448,
             -1762061251, -275165044, -427912809, -553764650, 1318605455, 2110050231, 1918128061, 0, -180492928,
             -141481531,
             -2125418106, 0, 896406095, 1945560325, 387287361, 1756344243, 993023407, -1918080037, -1595246967,
             -247374666,
             1700897371, 0, -558029971, 1281099722, 742220050, 382407707, 1083250902, 0, -660310043, 947326051,
             -899956981,
             1056444649, 1639102829, -1635196961, 606341580, -615430210, 1169029741, 565208772, -2029782273,
             -2118864171,
             -1376381130, -697891728, 437847401, 1884238345, -1197413398, -724522673, -303193826, 1520214848, 31928338,
             1508730160, -152353161, 287800407, 0, -1605308826, 1413220392, 0, -683454190, 189420289, -1538249830,
             -1511736337, -1473859405, -1928308173, -1023755936, 109556111, 2048167427, 1987982275, -580192887,
             -1134851337,
             -449851927, -1972802580, -699581560, -29923161, 112160044, -840561702, 0, -805456066, -241114153,
             120996477,
             -1660377328, -1328783761, -1644936411, 523804000, 950352839, 1379335877, -1632176544, -985330692,
             -1419146057,
             1492106653, 3284148, -1015702141, -1164224535, 806999227, -1026796965, 0, 288849588, 1088827806, 0,
             -868963690,
             337525146, 1239638671, 1612771108, -1834446232, 2141857483, 832876231, 777073603, -1335086389, -1501340576,
             -701641708, 871311318, 1746110302, 255943328, 91765485, 0, -73142092, -478780822, 1259718122, 688267890,
             -545733930, 0, -1698648458, 790045544, -1767542978, -511756137, -2066382101, 1418021593, 1998069484, 0,
             260883729, 0, -465752053, 1943124207, -221403354, 0, 1224054746, -1407756765, -1222229979, 343523086,
             -1954767674, 1637041446, 110309340, 1417534738, -684982413, -1850764935, 304940877, 1141640306,
             -1928613156,
             380575967, -1964303664, 1539220462, 1999971810, 744550895, -925335737, -477514863, 171081695, 1545922646,
             -2020471942, 758143322, -1817214847, 2005512009, 820881194, 0, 695104702, 951638873, -13483811, 1831578349,
             0,
             1371089166, -1653256682, 1338087892, 968398757, 1583375620, -1045058962, -1220116596, -1553054135,
             -1886092807,
             0, 0, -1990988022, 1179578188, -324221317, 1888449349, 1802081785, -1412931303, -780477237, 0, -326838880,
             0,
             403162699, 1675470066, 1761080459, -496635533, -1642678261, 2116383089, -318548165, -76068587, 801449758,
             545322261, -1275170749, 0, 1876136632, -273168632, 1897220212, 1999455304, -1904531754, -1556194471,
             1441218971, 0, -608179323, 25157503, 816447864, -1363565960, 0, 626471983, 287068317, 1458209427,
             -1938086614,
             -2001311984, 483404311, -697063475, 711796682, -35845798, 958229591, 209891262, 1485640719, 1628926181,
             -1708470607, 714553408, 1985121789, 514639764, -1229555770, 670258175, 1629272810, 0, 1414159171,
             309435511,
             1077067162, 290661932, 790066200, 1904089692, -340443786, 0, -1743484500, 311503271, 232107192, 2012677262,
             0,
             387696661, 1419829049, -782856182, -731718097, -1770103647, -1771987676, -891415795, -1487318178, 0,
             -836587758, -366263514, 1581212121, -1123466074, -1149662593, -927411396, 96718482, -1057204795,
             1212644014, 0,
             -396116333, -1985203832, 0, 1770701862, 996882452, 824174988, 0, -545515559, 1492106942, 836325927,
             -1234526190, 1535208608, 1415956773, 586281600, 347077244, 1417264403, 1907294625, -992130174, 483277071,
             -1747999072, -783136356, -1295809291, -240238264, -908648328, -230658546, 768537824, 165126852, 1189699727,
             602007856, 0, 820329431, 1991012001, 638797223, 1874954440, -276224051, -258684886, -961480201, 957222711,
             -2017715729, 1233626164, -1408248233, -810611491, -1881995109, 645370947, 1725636363, -1183468333,
             610398811,
             -649344739, 444827434, 351695686, -653124501, 862150385, 1018387891, -1161968739, -1396080037, -105789838,
             -1856051808, -951172745, 983520643, 564727267, 2080711782, 1024722381, 1592244508, -775465828, 425808086,
             889036357, 271129639, -1187760271, 1733776018, 492133104, 1104380122, -304035313, -933916079, -947371645,
             -1751571822, 0, -1505220410, 1949238241, 1822808023, -1275206227, -1286915787, 592200912, -1492686169,
             1259510995, -1851144610, 1576428177, 1972903552, 10347480, -852513686, -1226908000, 1544521056, 766397074,
             1529961761, 604772246, 642173143, 1125783039, -2100454000, 49102357, 608424097, 1774782031, 996782012,
             1227148247, 1576835819, -1447334882, 816725158, -1850264178, 43856448, 1905143789, -300346370, 0,
             -1433369716,
             2020448348, -799422695, 1583749860, 0, -2082209272, -1665220913, 199495242, 2018165260, 1882538990,
             1714892580,
             13541146, 0, 1781676377, 0, 1193272, 883668195, 0, -887007525, -1472607098, 1620460417, 567534089, 0, 0,
             966676357, -948828226, 0, -304202169, -1647146366, -1909805274, 1688192439, 0, 341643352, 1700375891,
             417728190, -457188089, 1612230319, -1569171854, 0, 762224785, 0, 0, -992952139, 1453139338, 1061284285,
             -248775260, -2134914393, -679955845, -735518230, 854860094, -1179860887, 272903692, 2089343740,
             -1437097694,
             -522758155, -817428090, 1909704206, 868511809, 1554042339, 1557286563, 629791102, 279650591, -128839316,
             -1959175012, 521768288, -963521197, -1959778475, 1140884863, 201269568, -748810752, -65626865, -968785349,
             456825539, -1966087165, 1393748811, -1386613228, 1427051729, -571750580, -1849492932, 1077907486,
             1387842944,
             1068881146, 1227200161, 1412640817, 1725653367, 368030240, 344412810, -1058725467, -133296507, -287863229,
             555889212, 0, -36739221]
    for i in [nums1, nums2]:
        print(s.moveZeroes(i))